U.S. Pat. No. 6,789,222 teaches complete test pattern generation methods for combinational circuits. The methods find all test patterns for all detectable faults for a combinational circuit. This result is accomplished during a single pass through a circuit-level sorted description of a combinational circuit (e.g., a netlist). The methods implement an incremental, breadth-first process that attempts to activate and to propagate faults through the circuit. Faults reaching circuit primary output lines define test patterns.
A sequential circuit can be represented as a combinational part and a separate feedback storage part (prior art FIG. 1). The circuit can be analyzed as an iterative array of the combinational parts, each containing a copy of the fault (prior art FIG. 2; see for example, K-T Cheng, “Tutorial and Survey Paper: Gate-Level Test Generation for Sequential Circuits,” ACM Trans. Design Automation of Electronic Sys., Vol. 1, No. 4, Oct. 1996, Pages 405-442).
The teachings of U.S. Pat. No. 6,789,222 can be applied to such an iterative array for generating test pattern sequences for sequentially detectable faults.
One way to do this is to create an array having a desired number of time-frames and to treat the array as a single, deep, combinational circuit. Use a data structure for path-enabling and for fault-propagation functions that is large enough to accommodate the single, deep, combinational circuit. The data structure size must represent a present-state and include one input vector for each time-frame of the array. Perform combinational test pattern generation on the single, deep, combinational circuit. Solving the problem this way, however, is impractical and limits the usefulness of the solution to very small sequential circuits and, at most, a few time-frames.
Another way to accomplish the desired result is to permit the data structures representing path-enabling and fault-propagation functions to begin at a size sufficient to handle a first time-frame. Then increase the data structure size to accommodate one additional input vector per additional time-frame. This solution, though complicated, permits slightly larger circuits or a few more time-frames to be handled. However, the function size grows rapidly and limits the size of the circuit and the number of time-frames. This approach too is impractical.
What is needed is a deterministic test pattern generator for sequential circuits that finds test pattern sequences for sequentially detectable faults during a single pass through an iterative array representation of a sequential circuit.
Such a test pattern generator should use a data structure having size equal to that of the data structure used during an initial combinational time-frame.
It should be unnecessary to predict a maximum number of time-frames that may be needed.
Finally, for all faults during all subsequent time-frames, the test pattern generator should reuse the path-enabling functions created during the initial combinational time-frame.